class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 0) return 0;
        return ((~K & 1)) ^ kthGrammar(N - 1, (K + 1) / 2);
   }
};